package solution;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ws
 * Date: 2023-04-01
 * Time: 20:56
 */

//https://leetcode.cn/problems/divide-two-integers/submissions/420162338/
class Solution {
    // 使用位运算，减法,二倍缩小扩大
    public int divide(int dividend, int divisor) {
        // MIN_VALUE 和 MAX_VALUE 的绝对值相差1，所以负数转正数，可能会越界
        //所以将正数全部转为负数，两个负数的商为正数，符号不同商*-1
        //用最高位来判断,>>> 无符号右移，^ 判断
        boolean flag = ((dividend >>> 31) ^ (divisor >>> 31)) == 1;
        //将正数全部转为负数
        if (dividend > 0) {
            dividend = -dividend;
        }
        if (divisor > 0) {
            divisor = -divisor;
        }
        //用来寻找最大商
        int mod = divisor;
        //被除数的一半,用于比较
        int minn = dividend >> 1;
        //记录除数不断扩大的倍数
        int now = -1;
        //先找出除数相对于被除数的最大商
        // 全为负数
        //即 最大商 > 被除数 >= (最大商) * 2
        while (mod >= minn) {
            mod <<= 1;//商不断二倍扩大
            now <<= 1;//记录扩大的倍数*2
        }
        //记录将除数的倍数，即商
        int ans = 0;
        //不断将被除数减最大商，同时最大商也随之改变，直到最大商等于除数
        //二倍缩小
        while (dividend <= divisor) {
            while (mod < dividend) {//让最大商始终大于被除数
                mod >>= 1;//商二倍缩小二倍
                now >>= 1;//记录的扩大的倍数除以二
            }
            //除数和被除数都为负数
            while (dividend <= mod) {//最大商大于被除数
                //（除法的实质就是减法）
                //最大商的目的就是减少相减的次数
                dividend -= mod;//被除数不断减最大商
                ans -= now;//记录除数的倍数
            }
        }
        //排除最小值的情况
        //MIN_VALUE 和 MAX_VALUE 的绝对值相差1，-MIN != -MAX
        //所以需要特殊处理
        if (ans == Integer.MIN_VALUE && !flag) {
            return Integer.MAX_VALUE;
        }
        //正数不用担心越界
        return flag ? -ans : ans;
    }
}